class Solution:
    def solveSudoku(self, board) -> None:
        blanks=[]
        for i in range(9):
            for j in range(9):
                if board[i][j]==".":
                    blanks.append((i,j))
        def findCandidates(pos):
            mark=[0 for i in range(9)]
            for i in range(9):
                try:
                    mark[int(board[i][pos[1]])-1]=1
                except ValueError:
                    pass
                try:
                    mark[int(board[pos[0]][i])-1]=1
                except ValueError:
                    pass
            palacex=pos[1]//3
            palacey=pos[0]//3
            for i in range(palacex*3,palacex*3+3):
                for j in range(palacey*3,palacey*3+3):
                    try:
                        mark[int(board[j][i])-1]=1
                    except ValueError:
                        pass
            return [i+1 for i in range(9) if mark[i]==0]
        def trySodoku(index):
            if index==len(blanks):
                return True
            candidates=findCandidates(blanks[index])
            for cand in candidates:
                board[blanks[index][0]][blanks[index][1]]=str(cand)
                if trySodoku(index+1):
                    return True
                else:
                    board[blanks[index][0]][blanks[index][1]]="."
            return False
        trySodoku(0)
        return board

s=Solution()
print(s.solveSudoku([["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]))